package com.lx.algorithm.ac;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-27 17:47:06
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-27     张李鑫                     1.0         1.0 Version
 */
public class Automation {
    public Node root;


    public Automation() {
        root = new Node();
    }

    public void insert(String content) {
        char[] chars = content.toCharArray();
        //记录一个遍历节点
        Node cur = root;
        for (int i = 0; i < chars.length; i++) {
            //遍历字符串 -a 代表在数组的索引
            int index = chars[i] - 'a';
            //如果有存在当前节点了 就不新建 如果不存在就新建
            if (cur.ways[index] == null) {
                cur.ways[index] = new Node();
            }
            //当前指针跳到 下一个指针
            cur = cur.ways[index];
        }
        //循环结束记录结束的点
        cur.endStr = content;
    }

    public List<String> containWords(String content) {
        char[] contents = content.toCharArray();
        ArrayList<String> list = new ArrayList<>();
        Node cur = root;
        Node follow = null;
        for (int i = 0; i < contents.length; i++) {
            //下条路的索引
            int index = contents[i] - 'a';
            while (cur.ways[index] == null && cur != root) {
                //如果不为空 并且不为root 就去fail指针
                //因为root的fail指针是null
                cur = cur.fail;
            }
            //判断一下是不是root 如果是root说明已经没有最长前缀路 就要开始重新匹配
            cur = cur.ways[index] != null ? cur.ways[index] : root;
            //循环指针
            follow = cur;
            //一直跳
            while (follow != root) {
                //如果被选择直接结束
                if (follow.isSelect) {
                    break;
                }
                // 如果是结束字符就记录
                if (follow.endStr != null) {
                    list.add(follow.endStr);
                    follow.isSelect = true;
                }
                // 跳到下一个fail节点
                follow = follow.fail;
            }
        }
        return list;

    }


    /**
     * 构建fail指针
     */
    public void build() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        //两个指针记录 当前节点跟 fail节点
        Node cur = null;
        Node fail = null;
        while (!queue.isEmpty()) {
            //弹出一个节点
            cur = queue.poll();
            //获取当前节点下面所有的路并遍历
            Node[] next = cur.ways;
            for (int i = 0; i < next.length; i++) {
                //如果有路
                if (next[i] != null) {
                    // 先把当前节点的fail节点挂在父亲节点上
                    // fail的处理的节点的流程是先挂在父亲上在去找
                    next[i].fail = cur;
                    //记录上个节点的fail
                    fail = cur.fail;
                    //如果不等于空 就查询当前上个节点是否有走到当前节点的路
                    //如果有几句把节点挂过去 没有的话 就跳到下一个fail节点 直到找不到位置
                    // 这样处理的可以直接连接到以当前为结束下一个最长的字符串
                    while (fail != null) {
                        if (fail.ways[i] != null) {
                            next[i].fail = fail;
                            break;
                        }
                        fail = fail.fail;
                    }
                }
                queue.add(next[i]);
            }
        }
    }

    public static void main(String[] args) {
        Automation automation = new Automation();
        automation.insert("as");
        automation.build();
    }
}
